1. Field of the Invention
The present invention relates to methods and apparatus for constructing a parity check matrix, and more particularly, to methods and apparatus for constructing a low-density parity check (LDPC) matrix, which can considerably reduce memory capacity of encoders and decoders in a low-density parity check (LDPC) coding scheme.
2. Related Art
Recently, various types of coding schemes have been proposed for communication and storage systems. One class of codes, generally referred to as low-density parity check (LDPC) codes, has been described as having good error detection and correction performance. In addition, LDPC codes can also be decoded at very high rates of speed. However, such LDPC codes are constructed by random choice of low-density parity check (LDPC) matrices, which require complex encoders and decoders with a large amount of memory.
For example, FIG. 1 shows matrices for explaining a concept of low-density parity check (LDPC) coding and decoding scheme. As shown in FIG. 1, the low-density parity check (LDPC) coding method generates parity information by using a low-density parity check matrix (H) whose elements are mostly 0's along with some “1”s.
In the parity check matrix (H), the number of “1”s in each row or column is referred to as row degree or column degree, respectively. Generally, a parity check matrix whose columns all have the same column degree and whose rows all have the same row degree is called a regular parity check matrix. A parity check matrix whose rows and columns do not all have the same row degree and column degree is called an irregular parity check matrix. In a regular parity check matrix, the row degree is referred to as row weight, Wr, and the column degree is referred to as column weight, Wc.
Parity information is generated on the basis of a low-density parity check (LDPC) coding scheme using the following Equation:HX=0  (1).
In Equation (1), H is an m×n parity check matrix, and X is an n×1 codeword matrix. X is comprised of m message information and p parity information, so that m+p=n.
A basic concept of LDPC coding is disclosed by D. J. MacKay, “Good Error-correction Codes Based on Very Sparse Matrices”, IEEE Trans. on Information Theory, vol. 45, no. 2, pp. 399-431, 1999. D. J. Mackay discloses that parity information is generated by solving Equation (1) with a matrix algebra, such as a Gaussian Elimination method.
Parity check decoding also includes a procedure for performing a parity check on the basis of Equation (1).
There are basically two different techniques of constructing a conventional parity check matrix of LDPC codes. In the first technique, row indexes, which indicate row positions of each “1” in each column of the parity check matrix H, are arbitrarily set by a user. For example, row indexes of 1, 3, and 5 may be set for the first column, row indexes of 2, 4, and 6 may be set for the second column, 7, 9, and 11 may be set for the third column, and so forth. This technique can be easily implemented, but has poor bit error rate (BER) performance. In the second technique, row indexes, which indicate row positions of “1” in each column of the parity check matrix H, are determined randomly. Implementation of the second technique is more complicated since row positions (indexes) of “1”s are randomly distributed. However, the second technique of constructing parity check matrix of LDPC codes has excellent BER performance.
An example of the second technique of constructing the parity check matrix will now be described as follows.
First, Wc row indexes of element “1”s in the first column are determined. Next, arbitrary row indexes of “1”s in the second column are determined such that none is the same as row indexes of “1”s in the first column. Then, arbitrary row indexes of “1”s for the third column are determined such that none is the same as row indexes of “1”s in the first and second columns. This procedure is repeated through to the last column.
In summary, in the second technique of constructing a parity check matrix, row indexes of “1”s in each column of the parity check matrix H are set arbitrarily as long as no two columns have the same row index.
According to the second technique of constructing the parity check matrix, previously determined row indexes of “1”s should be stored in a memory of an apparatus for constructing the parity check matrix. Also, for encoding or decoding purposes, all the row indexes of “1”s should be stored in a memory of an encoder or a decoder.
FIG. 2 shows a memory structure for storing a parity check matrix. As shown in FIG. 2, the memory can be a random-access memory (ROM) 20. The parity check matrix can be defined by row indexes of “1”s, which represent positions of “1”s in each column, and column indexes of “1”s, which represent positions of “1”s in each row. A parity check matrix H which is defined by row indexes of “1”s is stored in the memory 20 for encoding and decoding purposes.
As also shown in FIG. 2, one row index of “1” occupies one address of the memory 20. Consequently, the space occupied by one parity check matrix is n×Wc×B. Here, B is the number of bits of a row index of the “1”, and 2B=m, where m is the number of rows of the parity check matrix.
An example of an m×n parity check matrix having satisfactory BER error correction performance is a 512×(512×17) parity check matrix. The memory space required to store the m×n parity check matrix is 512(=29)×(512×7)×9 bits. Generally, achieving better BER performance requires using large amounts of memory to store the parity check matrix. However, using large amounts of memory causes several problems, such as, for example, a substantial increase in the cost of producing corresponding encoders and decoders.